import java.util.HashMap;
public class Lru {
    //双向链表的结点
        class Node{
            int key;
            int val;
            Node next;
            Node pre;
            public Node(){}
            public Node(int key,int val){
                this.key=key;
                this.val=val;
                this.next=null;
                this.pre=null;
            }
        }
        //hashmap存key，若能检索到key则表示在缓存中
        HashMap<Integer,Node> hash=new HashMap<Integer,Node>();
        //当前缓存内数量
        int size;
        //缓存所能存的最大值
        int capacity;
        //链表头，他的下一个结点是最近最不常用的，若需要替换，则替换掉该节点的下一个结点
        Node first;
        //链表尾，他的上一个结点是最近使用的
        Node last;
        public Lru(int capacity) {
            this.size=0;
            this.capacity=capacity;
            this.first=new Node();
            this.last=new Node();
            first.next=last;
            last.pre=first;
        }

        public int get(int key) {
            Node n=hash.get(key);
            if(n!=null){
                //get（）执行后需要把该结点放至链表尾
                Node pre=n.pre;
                Node nex=n.next;
                if(nex!=last){
                    nex.pre=pre;
                    pre.next=nex;
                    n.pre=last.pre;
                    last.pre.next=n;
                    n.next=last;
                    last.pre=n;
                }
                return n.val;
            }else{
                return -1;
            }
        }

        public void put(int key, int value) {
            Node n=hash.get(key);
            if(n!=null){
                //若缓存中存在原来的索引，则把该结点放至链表尾，并修改val值
                Node pre=n.pre;
                Node nex=n.next;
                if(nex!=last){
                    nex.pre=pre;
                    pre.next=nex;
                    n.pre=last.pre;
                    last.pre.next=n;
                    n.next=last;
                    last.pre=n;
                }
                n.val=value;
            }else{
                //不存在先判断是否需要缓存替换
                if(size==capacity){
                    int k=first.next.key;
                    hash.remove(k);
                    first.next=first.next.next;
                    first.next.pre=first;
                    size--;
                }
                n=new Node(key,value);
                n.pre=last.pre;
                last.pre.next=n;
                n.next=last;
                last.pre=n;
                hash.put(key,n);
                size++;
            }
        }
    }
